Interlacing methods in Extremal Combinatorics

Abstract: Extremal Combinatorics studies how large or how small a collection of finite objects could be, if it has to satisfy certain restrictions. In this talk, we will discuss how eigenvalue interlacing leads to various interesting results in Extremal Combinatorics, including the Erdos-Ko-Rado Theorem and its degree version, an isodiametric inequality for discrete cubes, and the resolution of a thirty-year-old open problem in Theoretical Computer Science, the Sensitivity Conjecture.

Mathematics

Audience: researchers in the topic

ICCM 2020